<?php
require_once($_SERVER['DOCUMENT_ROOT'] . "/config.php");

include ABS_PATH . "header.php"; 
include ABS_PATH . "navigation.php"; 
include ABS_PATH . "menu.php"; 

// navigation starts here
global $cur_option;
$cur_option = "Engine";
menu($cur_option);
?>


<?php include ABS_PATH . "after-navigation.php"; ?>
            <!-- add your content here -->
<?php
// Main engine	

// include_once ABS_PATH . "misc/functions.php"; // to get _log etc.

include_once ABS_PATH ."engine/functions.php"; // these are REALLY local to the engine!

/*
echo "Trying to open database " . PDO_PREFIX . SQLITE_DB_FILENAME . (file_exists(SQLITE_DB_FILENAME) ? (" (file exists)") : (" (file does NOT exist)")) . "<br />\n";

echo "Dumping database...<br />\n<br />\n";

$string = file_get_contents(SQLITE_DB_FILENAME);
echo "Size of database: " . strlen($string);

echo "<br />\n";
*/

// open database	
try {
	$db = new PDO(PDO_PREFIX . SQLITE_DB_FILENAME);
}	
catch(PDOException $e)
{
	header("HTTP/1.0 503 Service Unavailable");
	printf("Connect failed: %s\n", $e->getMessage());
   	_log(__FILE__ . " - line " . __LINE__ . ": Error connecting to database: " . $e->getMessage());
    exit();
}

echo "<p class='box'>Database open.</p>\n";
echo "<h2>Stats</h2>\n";
echo "<p>Obstacles: ";

$obstacles = $agents = $cubes = array();

try {
	$SQL = "SELECT * FROM Obstacles WHERE Phantom = 0"; // do not 'see' phantom items!!
	$sth = $db->prepare($SQL);
	$sth->execute();
	$obstacles = $sth->fetchAll(PDO::FETCH_ASSOC);	// we need them inside anyway
	// var_dump($obstacles);
	echo count($obstacles) . " (without phantom items)</p>";
}
catch(PDOException $e)
{
	_log(__FILE__ . ":" . __LINE__ . " No rows for query $SQL");
	die("Couldn't execute query $SQL: " . $e->getMessage() . "<br />\n");
}

// Get agents

echo "<p>Agents: ";

try {
	$SQL = "SELECT * FROM Agents";
	$agentHandler = $db->prepare($SQL);
	$agentHandler->execute();
	$agents = $agentHandler->fetchAll(PDO::FETCH_ASSOC);	// we need them inside anyway
	// var_dump($agents);
	echo count($agents) . "</p>";
}
catch(PDOException $e)
{
	_log(__FILE__ . ":" . __LINE__ . " No rows for query $SQL");
	die("Couldn't execute query $SQL: " . $e->getMessage() . "<br />\n");
}

// Get cubes (we call them Positions in the database; at some point I might change the names back)

echo "<p>Cubes (without Master Bot Controllers): ";

try {
	$SQL = "SELECT * FROM Positions WHERE ObjectType <> 'Bot Controller'";
	$cubesHandler = $db->prepare($SQL);
	$cubesHandler->execute();
	$cubes = $cubesHandler->fetchAll(PDO::FETCH_ASSOC);	// we need them inside anyway
	// var_dump($cubes);
	echo count($cubes) . "</p>";
}
catch(PDOException $e)
{
	_log(__FILE__ . ":" . __LINE__ . " No rows for query $SQL");
	die("Couldn't execute query $SQL: " . $e->getMessage() . "<br />\n");
}

if (!isset($_REQUEST["Destination"]))
{
	if (empty($agents))
	{
		echo "<p class='box warning'>No agents found.</p>\n";
	}
	else
	{
?>
		<form class="ym-form" action="index.php">
				<div class="ym-fbox">
					<div class="ym-fbox-wrap ym-grid">
						<div class="ym-g33 ym-gl">
							<div class="ym-gbox-left">
								<select name="Destination" id="Destination" size="1">
									<option value="0" selected="selected" disabled="disabled">Please choose a destination cube</option>
<?php		
		foreach ($cubes as $cube)
		{
			$regionName = substr($cube["Location"], 0, strpos($cube["Location"], "(") - 1);
            $coords = trim($cube["Position"], "() \t\n\r");
            $xyz = explode(",", $coords);
			
			printf('\t\t<option value="%s">%s [%s (%d,%d,%d)]</option>\n',
				$cube['UUID'], $cube['Name'],
				$regionName, $xyz[0], $xyz[1], $xyz[2]);
		}
?>
								</select>
							</div>
							<div class="ym-gbox-left">
								<select name="Agent" id="Agent" size="1">
									<option value="0" selected="selected" disabled="disabled">Please choose an agent</option>
<?php		
		foreach ($agents as $agent)
		{
			$regionName = substr($agent["Location"], 0, strpos($agent["Location"], "(") - 1);
			$coords = trim($agent["Position"], "() \t\n\r");
			$xyz = explode(",", $coords);
		
		printf('\t\t<option value="%s">%s [%s (%d,%d,%d)]</option>\n',
			$agent['UUID'], $agent['Name'],
			$regionName, $xyz[0], $xyz[1], $xyz[2]);
		}
?>
								</select>					
							</div> <!-- ym-gbox-left -->
						</div> <!-- ym-g33 ym-gl -->
					</div> <!-- ym-fbox-wrap ym-grid -->
				</div> <!-- ym-fbox -->
				<div class="ym-fbox-footer">
					<div class="ym-fbox-wrap ym-grid">
						<div class="ym-g20 ym-gl">
							<div class="ym-gbox-left">
								<input type="submit" class="ym-button ym-primary" value="Submit" id="submit"/>
							</div>
						</div>
						<div class="ym-g20 ym-gl">
							<div class="ym-gbox-right">
								<input type="reset" class="ym-button ym-warning" value="Reset" id="reset"/>
							</div>
						</div>
					</div>
				</div> <!-- ym-fbox-footer -->
		</form>
						
							
<?php
	} // end if (empty($agents))

} // end !isset($_REQUEST("Destination"))
else
{
	echo "<h2>Running...</h2>\n";
	
	// Start with first agent; probably we'll have checkboxes for the agents, we'll see
	if (empty($agents))
	{
		echo "<p class='box warning'>No agents found.</p>\n";
	}
	else 
	{
		// $_REQUEST["Agent"] has UUID for the agent we should move
		// To make this compatible with our previous code, we'll just assign $agent to the correct agent data
		
		$agent = array();
		
		foreach ($agents as $ag)
		{
			if ($ag['UUID'] == $_REQUEST["Agent"])
				$agent = $ag;
		}
		
		if (empty($agent))
		{
			echo "<p class='box error'>Agent " . $_REQUEST["Agent"] . " not found!!</p>\n";

		}
		
		// prepare data to be saved as a CSV/XML file for later import into Excel and do nice graphics
		$export_rows = array(); // we place it here because of potential scope issues later on...
	
		// What follows is just statistical data
	
		$SQL = "SELECT * FROM Positions WHERE ObjectType ='Bot Controller' ORDER BY LastUpdate DESC LIMIT 1";
		$mCtrlHandler = $db->prepare($SQL);
		$mCtrlHandler->execute();
		$masterController = $mCtrlHandler->fetch(PDO::FETCH_ASSOC);
			
		// foreach ($agents as $agent)
		//{
			// Everything is borked, so commands now go through the Master Controller
			// get first agent's position
			// Ask inworld for its position
		
			echo "<h3>" . $agent['OwnerName'] . "</h3>\n";
			echo "Database thinks it's at " . $agent['Position'] . "<br />\n";
		
			// die("here");
		
			$curPos_raw = callURL($masterController['PermURL'], "npc=" . $agent['OwnerKey'] . "&command=osNpcGetPos");
			if (!$curPos_raw)
			{
				echo "Agent " . $agent['OwnerName'] . " asleep; skipping<br />\n";
				continue;
			}
		
			echo "Agent " . $agent['OwnerName'] . " is currently at " . $curPos_raw . "<br />";
			
			try
			{			
				$dbh = $db->exec("UPDATE Agents SET Position = '" . trim($curPos_raw, " ()<>")
					. "' WHERE OwnerKey = '" . $agent['OwnerKey'] . "'");
			}
			catch (PDOException $e)
			{
				_log(__FILE__ . ":" . __LINE__ . " Couldn't update agent position for " . $agent['OwnerName']
					. "; error: " . $e->getMessage());
				echo(" Couldn't update agent position for " . $agent['OwnerName']
					. "; error: " . $e->getMessage() . "<br />\n");
				// not critical, it will get updated sooner or later
			}	
			
			$curPos = explode(",", trim($curPos_raw, " <>()\t\n\r\0\x0B")); // sanitize
			
					
			// calculate distances to nearest obstacles
	
			$smallestDistanceToObstacle = 1024.0; // will be used later on
			$nearestObstacle = array();
			$smallestDistanceToCube = 1024.0; // will be used later on
			$nearestCube = array();
			
			foreach ($obstacles as $point)
			{
				echo "Obstacle: " . $point['Name'] . " - " . $point['Position'] . "<br />";
				
				$obstaclePosition = explode(",", $point['Position']);
				$distance = distance($curPos, $obstaclePosition);
				// echo " Distance between: (us) " . print_r($curPos, true) . " and (obstacle) " . print_r($obstaclePosition, true) . " = " . $distance . "<br />\n";
				if ($distance < $smallestDistanceToObstacle) 
				{
					$smallestDistanceToObstacle = $distance;
					$nearestObstacle = $point;
				}
			}
			echo "<b>Nearest obstacle:</b> " . $nearestObstacle['Name'] . " (at " . $smallestDistanceToObstacle . ")<br />\n";
		
			// calculate distances to cubes
			// should test if it's the correct class of cubes!
		
			foreach ($cubes as $cube)
			{
				echo "Cube: " . $cube['Name'] . " - " . $cube['Type'] . " - " . $cube['Position'] . "<br />";
				
				$cubePosition = explode(",", $cube['Position']);
				// echo " Distance between: (us) " . print_r($curPos, true) . " and (cube) " . print_r($cubePosition, true) . " = " . $distance . "<br />\n";
				$distance = distance($curPos, $cubePosition);
				if ($distance < $smallestDistanceToCube)
				{
					$smallestDistanceToCube = $distance;
					$nearestCube = $cube;
				}
			}
			echo "<b>Nearest cube:</b> " . $nearestCube['Name'] . " (at " . $smallestDistanceToCube . ")<br />\n";
	
	/* Idea for the GA
	
	1. Start with a 20x20 matrix (based loosely on Cosío and Castañeda) around the bot, which contain sensor data (we just sense up to 10 m around the bot). This might need adjustment (i.e. smaller size). 
	This represents the space of possible solutions
	Active cube will determine attraction point (see later)
	Chromosomes: randomly generated points (inside the 20x20 matrix) that the robot has to travel. Start perhaps with 50 with a length of 28 (Castañeda use 7 for 10x10 matrix). Points are bounded within the 20x20 matrix
	Now evaluate each chromosome with fitness function:
	- for each point: see if it's "too near" to an obstacle (potential collision)
		- ray casts are more precise, so give it a highest weight (not implemented yet)
		- normal sensor data give lower weigth
		- we can add modifiers: see number of prims of each obstacle (more prims, more weight, because object might be bigger than predicted); see if the obstacle is an agent (initially: agents might act as deflectors; later: interaction matrix will see if the bot goes nearer to the agent or avoids it)
	- for each point: see if it's closest to the cube. Lowest distance reduces weight. In theory, we wish to find the path with the least distance (less energy wasted)
	- sort chromosomes according to fitness
	- do 20 generations and find next expected point. Move bot to it. Reduce energy calculation on bot. See if it dies!
	- repeat for next bot position
	
	20130520 — Results don't converge. It's hard to get the 'bot in less than a 10m radius.
	Attempt #2 - use a 10x10 matrix, just 7 points, like Castañeda
	Gotshall & Rylander (2002) suggest a population size of about 100-200 for 7 chromosomes
	Attempt #3 - Algorithm from Ismail & Sheta was badly implemented!! 
	Attempt #4 - (to-do) implement Shi & Cui (2010) algorithm for fitness function
	Attempt #5 - Shi & Cui (2010) use a strange way to calculate path smoothness. Attempting Qu, Xing & Alexander (2013) which use angles. Modified mutation function, instead of the classical approach (switching two elements in the path), add random ±x, ±y to point
	André Neubauer (circular schema theorem, cited by Qu et al.) suggest two-point crossover
	Qu et al. suggest sorting path points, after crossover/mutation
	#6 - refinations on #5 - based on E. Pires solution, use square distances, and make sure to include the destination point into the individual space if it is within radius
	
	*/
	
	/*		goal/target/attractor: where the 'bot is going to go next
			at some point, this ought to be included in the chromosome as well
			for now, we'll hard-code it (walk to the nearest cube)
			on stage two, we'll do a simple check:
				- see what attributes are lowest
				- go to the nearest cube that replenishes the attribute
				- since this will be iterated every time the 'bot moves, we hope it won't die from starvation,
					as moving elsewhere becomes prioritary
	*/
			
			// $nearestCube is where we go (20140526 changing it to selected cube by user, named $destCube)
	
			// Genetic algorithm for movement
			// generate 50 strings (= individuals in the population) with 28 random points (= 1 chromosome) at curpos ± 10m
			
			$time_start = microtime(true);
			
			$population = array();	// should be an array of objects, we're doing it quick & dirty for now
	
			// We calculate now the distance from each point to the destination
			//  Because this is computationally intensive, we will not repeat it every time during each generation
			//  Works well unless the destination moves! Then our calculations might be wrong
			//  But we will catch up on the _next_ iteration (hopefully, unless it moves too fast)
			//  We also use the best and second best path from a previous run of the GA		
			
			// get from the database the last two 'best paths' (if it makes sense)
					
			$start_pop = 0; // if we have no best paths, we will generate everything from scratch
			
			// Maybe it makes sense to keep around the last best paths if we're still moving towards the same
			//  cube; so check for this first, and discard the last best paths if the destination changed
			
			// First, to make the code reasonably compatible, let's fetch the destination cube from the form
			//  and assign it to 'destCube'
			
			$destCube = array();
						
			if (isset($_REQUEST['Destination']))
			{
				foreach ($cubes as $c)
				{
					if ($c['UUID'] == $_REQUEST["Destination"])
						$destCube = $c;
				}
			}
			
			// if we cannot find a destination cube, either on the form, or because the database is borked,
			//  we just use the nearest cube instead.
			if (empty($destCube))
			{
				echo "<p class='box warning'>Cube " . $_REQUEST["Destination"] . " not found; using nearest cube instead</p>\n";
				$destCube = $nearestCube;
			}

			$cubePosition = explode(",", $destCube['Position']);
					
			if ($destCube['Position'] == $agent['CurrentTarget'])
			{
				echo "<p class='box success'>Current target (" . $destCube['Name'] . ") is the same as before: " 
					. $cubePosition[0] . "," . $cubePosition[1] . "," . $cubePosition[2]
					. "</p>\n";
			
				/*
				$BestPath = unserialize(base64_decode($agent['BestPath']));
				if (!is_array($BestPath) || empty($BestPath))
				{
		        	// something went wrong, initialize to empty array
					$BestPath = array();
				}
				else
				{
					$population[$start_pop] = $BestPath;
					$start_pop++;
				}
		
				$SecondBestPath = unserialize(base64_decode($agent['SecondBestPath']));
				if (!is_array($SecondBestPath) || empty($SecondBestPath)) 
				{
					$SecondBestPath = array();
				}
				else
				{
					$population[$start_pop] = $SecondBestPath;
					$start_pop++;
				}
				*/
			}
			else
			{
				echo "<p class='box warning'>Current target is " . $destCube['Name']
					. " (at " . $cubePosition[0] . "," . $cubePosition[1] . "," . $cubePosition[2]
					. ") and we used to be moving towards " . $agent['CurrentTarget'] . "</p>\n";
			}
			
			// calculate the center point between current position and target
			// needs to be global for path sorting function (Ruhe's algorithm)
			global $centerPoint;
			
			$centerPoint = array(
				"x" => 0.5 * ($cubePosition[0] + $curPos[0]),
				"y" => 0.5 * ($cubePosition[1] + $curPos[1]),
				"z" => 0.5 * ($cubePosition[2] + $curPos[2])
			);
			
			// Now generate from scratch the remaining population
			 
			for ($i = $start_pop; $i < POPULATION_SIZE; $i++)
			{
				$population[$i]["fitness"] = 0.0;
	
				for ($y = 0; $y < CHROMOSOMES; $y++)
				{
					// Ismail & Sheta recommend to use the distance between points as part of the fitness
					// edge cases: first point, which is the distance to the current position of the agent
					// and last point, which is the distance between the last point and the target
					// that's why the first and last point have been inserted differently in the population
				
					if ($y == 0) // first point is (approx.) current position
					{
						$population[$i][$y]["x"] = intval($curPos[0]);
						$population[$i][$y]["y"] = intval($curPos[1]);
						$population[$i][$y]["z"] = intval($curPos[2]);
					}
					elseif ($y == (CHROMOSOMES - 1)) // last point is (approx.) position of target
					{
						$population[$i][$y]["x"] = intval($cubePosition[0]);
						$population[$i][$y]["y"] = intval($cubePosition[1]);
						$population[$i][$y]["z"] = intval($cubePosition[2]);					
					}
					else // others are scattered around the current position
					{
						$population[$i][$y]["x"] = intval($curPos[0] + mt_rand(-RADIUS, RADIUS));				
						if ($population[$i][$y]["x"] < 0) $population[$i][$y]["x"] = 0;
						elseif ($population[$i][$y]["x"] > 255) $population[$i][$y]["x"] = 255;
						
						$population[$i][$y]["y"] = intval($curPos[1] + mt_rand(-RADIUS, RADIUS));
						if ($population[$i][$y]["y"] < 0) $population[$i][$y]["y"] = 0;
						elseif ($population[$i][$y]["y"] > 255) $population[$i][$y]["y"] = 255;
						
						$population[$i][$y]["z"] = intval($centerPoint["z"]); // will work for flat terrain but not more
					}
					
					/*
					// if distance to any obstacle is less than 1, consider that point as "too close"
					// this uses brute force, and is not really very efficient
					
					$population[$i][$y]["obstacle"] = false;
					foreach ($obstacles as $point)
					{
						$obstaclePosition = explode(",", $point['Position']);
						$distance = distance(
							array(
								$population[$i][$y]["x"],
								$population[$i][$y]["y"],
								$population[$i][$y]["z"]
							),
							$obstaclePosition);
							
						if ($distance < 1.0)
						{
							$population[$i][$y]["obstacle"] = true;
							// should we discard it??
						}
					}
					*/
					
					// To implement Shi & Cui (2010) or Qu et al. (2013) we add these distances to obstacles together
					//  If there are no obstacles in our radius, then we keep it clear
	
					$population[$i][$y]["obstacle"] = RADIUS; // anything beyond that we don't care
					foreach ($obstacles as $point)
					{
						$obstaclePosition = explode(",", $point['Position']);
						$distance = distance(
							array(
								$population[$i][$y]["x"],
								$population[$i][$y]["y"],
								$population[$i][$y]["z"]
							),
							$obstaclePosition);
							
						// Shi & Cui and Qu et al. apparently just uses the distance to the nearest obstacle
						if ($distance < $population[$i][$y]["obstacle"])
							$population[$i][$y]["obstacle"] = 1/$distance;
							// we use the inverse here, because if we have many distant obstacles it's
							//  better than a single one that is close by
							
						// to-do: obstacles flagged as ray-casting are far more precise, so they ought to be
						//  more weighted
						
						// to-do: obstacles could also have bounding box calculations: bigger objects should
						//  be more weighted. However, HUGE objects might have holes in it. We ought to
						//  include the bounding box only for ray-casting, or else navigation would be impossible!
						//  Note that probably OpenSim raycasts only via bounding boxes (need confirmation)
						//  so maybe this is never a good approach. Lots of tests to be done here!
					}
					if ($population[$i][$y]["obstacle"] == RADIUS)
						$population[$i][$y]["obstacle"] = 0.0;
	
					// calculate, for this point, its distance to the destination, currently $destCube
					// (exploded to array $cubePosition)
					// might not need this 
					
					$population[$i][$y]["distance"] = distance(
							array(
								$population[$i][$y]["x"],
								$population[$i][$y]["y"],
								$population[$i][$y]["z"]
							),
							$cubePosition);
						
					// abandoned: initialize smoothness for Shi & Cui
					// adopted (20140523): smoothness using angles, like Qu et al.
					$population[$i][$y]["smoothness"] = 0.0;
					$population[$i][$y]["angle"] = 0.0; // maybe initialize it here
				} //endfor $y
				
				// now sort this path. According to Qu et al. (2013) this gets us a smoother path
				// hope it's true, because it's computationally intensive
				// (20140523) we're using Ruhe's algorithm for sorting according to angle, hope it works
				// (20140524) Abandoned Ruhe, using a simple comparison like Qu et al.
				//echo "Before sorting, point $i is: "; var_dump($population[$i]); echo "<br />\n";
				/*
				$popsort = substr($population[$i], 1, -1);
				$first_individual = $population[$i][0];
				$last_individual  = $population[$i][CHROMOSOMES - 1];
				usort($popsort, 'point_cmp');
				$population[$i] = 	array_merge((array)$first_individual, $popsort, (array)$last_individual);
				*/
				usort($population[$i], 'point_cmp');
				
				//echo "After sorting. point $i is: "; var_dump($population[$i]); echo "<br />\n";
			} // endfor $i
	
			// We're not finished yet! We need to calculate angles between all points (duh!) to establish smoothness
			// Let's do it from scratch:		
			
			for ($i = 0; $i < POPULATION_SIZE; $i++)
			{
				$population[$i][0]["angle"] = 0.0; // curPos has (obviously) angle 0
				
				for ($j = 1; $j < CHROMOSOMES; $j++)
				{
					$population[$i][$j]["angle"] = abs(
						atan2($population[$i][$j]["y"] - $population[$i][$j-1]["y"], 
						$population[$i][$j]["x"] - $population[$i][$j-1]["x"]));
				}
			}
			
			// Initial population done; now loop over generations
			
			for ($generation = 0; $generation < GENERATIONS; $generation++)
			{
				// Calculate fitness
				// echo "<hr /><p>Generating fitness for generation " . $generation . " (out of " . GENERATIONS . ") ...</p>";	
	
				// When calculating a new population, each element will have its chromosomes reordered
				//  So we have no choice but to calculate fitness for all population elements _again_
				for ($i = 0; $i < POPULATION_SIZE; $i++)
				{
					$fitnessW1 = $fitnessW2 = $fitnessW3 = 0.0;
					
					// note that first point is current location; we start from the second point onwards
					for ($y = 1; $y < CHROMOSOMES; $y++)
					{
	
						// Sub-function of Path Length (using Shi & Cui)
						
						$distLastPoint = distance(array(
									$population[$i][$y]["x"],
									$population[$i][$y]["y"],
									$population[$i][$y]["z"]
								),
								array(
									$population[$i][$y-1]["x"],
									$population[$i][$y-1]["y"],
									$population[$i][$y-1]["z"]
								));
								
						// Eduardo: suggests using square distance, means path will have more
						//  distributed points. (20140704 - 2004)
												
						$fitnessW1 += pow($distLastPoint, 2);
						
						// Sub-function of Path Security (using Shi & Cui) — obstacle proximity
						
						$fitnessW2 += $population[$i][$y]["obstacle"];
						
						// Sub-function of Smoothness (using Shi & Cui)
						// This measures how zig-zaggy the path is, namely, if points are pointing back etc.
						// We want a smooth path towards the goal
						// Possibly here is where the weight will be added
						// Attempt #5: Qu et al. suggest the angle between line segments
						// used http://stackoverflow.com/questions/20395547/sorting-an-array-of-x-and-y-vertice-points-ios-objective-c
						
						/* Shi & Cui; abandoned
						$population[$i][$y]["smoothness"] =
							(
								($population[$i][$y-1]["y"] - $population[$i][$y]["y"]) /
								($population[$i][$y-1]["x"] - $population[$i][$y]["x"])
							)
							-
							(
								($population[$i][$y]["y"] - $population[$i][$y-1]["y"]) /
								($population[$i][$y]["x"] - $population[$i][$y-1]["x"])
							);
						*/
						
						$fitnessW3 += abs($population[$i][$y]["angle"]); // clever, huh? check if abs makes sense
						
						// and we'll also use the overall distance to the attractor
						//$population[$i]["fitness"] += $population[$i][$y]["distance"];
					} // end for $y
					$population[$i]["fitness"] = W1 * $fitnessW1 + W2 * $fitnessW2 + W3 * $fitnessW3;
					
				} // end for $i
				
				// note that the most critical point is the first: it's the one the 'bot will try to walk to. But we need
				//  to calculate the rest of the path, too, which is "the best path so far which the bot plans to travel"
				//  even if at every iteration, it will get calculated over and over again
				
				/*
				$time_end = microtime(true);
				$time = $time_end - $time_start;
		
				echo "<p>CPU time used after fitness calculations for generation " . $generation . ": " . $time
					. " seconds</p>\n";
				
				
				echo "Generation " . $generation . " - Before ordering: <br />\n";
				showPopulation($population);
				echo "<br />\n";
				*/
				
				// Now we do genetics!
		
				// To pick the 'best' population elements, we need to sort this by fitness, so that the best
				//  elements are at the top
				
				// order by fitness, using our auxiliary function (see functions.php)
				if (!usort($population, 'cmp'))
				{
					echo "<p class='box error'>DANG! Sort failed for generation $generation!</p>";
				}
				/*
				echo "Generation " . $generation . " - After ordering by fitness: <br />\n";
				showPopulation($population);
				echo "<br />\n";
				
				$time_end = microtime(true);
				$time = $time_end - $time_start;
		
				echo "<p>CPU time used after sorting this generation: " . $time . " seconds</p>\n";
				*/
				
				// Selection step. We're using fitness rank
				
				$newPopulation = array();
				
				// To introduce elitism, we will move the first 2 elements to the new population:
				$newPopulation[0] = $population[0];
				$newPopulation[1] = $population[1];
				// we could also delete the remaining two
						
				// for the remaining population:
				for ($i = 2; $i < POPULATION_SIZE; $i += 2) 
				{
					// establish if we do crossover
					if (mt_rand(0, 100) < CROSSOVER_RATE)
					{		
						// find a crossover point; according to André Neubauer, we might need two crossover points
						$crossover_point = mt_rand(0, CHROMOSOMES-1);
						$child0 = array();
						$child1 = array();
					
						// echo "Generation " . $generation . " - Crossover for " . $i . " and " . ($i + 1) . " happening at crossover point: " . $crossover_point . "</br>\n";
						
						// now copy the chromosomes from the first parent, up to the crossover point, to $child0
						//  and the remaining chromosomes go to the second child
						// simultaneously, do the reverse for the second parent
						
						// there are probably better/faster string manipulation techniques but this is easy to debug
						for ($chromosome = 0; $chromosome < CHROMOSOMES; $chromosome++)
						{
							if ($chromosome <= $crossover_point)
							{
								$child0[$chromosome] = $population[$i][$chromosome];
								$child1[$chromosome] = $population[$i+1][$chromosome];
							}
							else
							{
								$child0[$chromosome] = $population[$i+1][$chromosome];
								$child1[$chromosome] = $population[$i][$chromosome];						
							}
							/* 
							echo "Pop " . $i . ", chromosome: " . $chromosome . " Original chromosome: ";
							print_r($population[$i][$chromosome]);
							echo " Child 0 chromosome: ";
							print_r($child0[$chromosome]);
							echo "<br />\n";
							*/
						} // endif chromosomes
						
						// test for mutation; note that this is permille and not percent
						if (mt_rand(0, 1000) < MUTATION_RATE)
						{
							/*
								Abandoned mutation implementation, which was a classical formulation
								for value-based GA (as opposed to bit-based)
								
							// pick two chromosomes for first child, two for second child
							//  see http://obitko.com/tutorials/genetic-algorithms/crossover-mutation.php
							
							$first_chromosome = mt_rand(0, CHROMOSOMES-1);
							$second_chromosome = mt_rand(0, CHROMOSOMES-1);
							// exchange them, by using a temporary holder (this is mostly because
							//  the exchange might be for the same chromosome!
							$temp_first_chromosome = $child0[$first_chromosome];
							$temp_second_chromosome = $child0[$second_chromosome];
							
							$child0[$first_chromosome] = $temp_second_chromosome;
							$child0[$second_chromosome] = $temp_first_chromosome;
	
							// echo "Generation " . $generation . " - Mutation happening for child " . $i . " — exchanging chromosomes " . $first_chromosome . " and " . $second_chromosome . "</br>\n";
							
							// same for second child
	
							$first_chromosome = mt_rand(0, CHROMOSOMES-1);
							$second_chromosome = mt_rand(0, CHROMOSOMES-1);
							// exchange them, by using a temporary holder (this is mostly because
							//  the exchange might be for the same chromosome!
							$temp_first_chromosome = $child1[$first_chromosome];
							$temp_second_chromosome = $child1[$second_chromosome];
							
							$child1[$first_chromosome] = $temp_second_chromosome;
							$child1[$second_chromosome] = $temp_first_chromosome;
	
							// echo "Generation " . $generation . " - Mutation happening for child " . ($i + 1) . " — exchanging chromosomes " . $first_chromosome . " and " . $second_chromosome . "</br>\n";
							
							*/
							
							/*
								(20140523) Instead, as Qu et al. do, just pick a point and add some 
								random distance to it
							*/
							$first_chromosome = mt_rand(0, CHROMOSOMES-1);
							$second_chromosome = mt_rand(0, CHROMOSOMES-1);
							
							$child0[$first_chromosome]["x"] += mt_rand(-RADIUS/2, RADIUS/2);
							if ($child0[$first_chromosome]["x"] < 0) $child0[$first_chromosome]["x"] = 0;
							elseif ($child0[$first_chromosome]["x"] > 255) $child0[$first_chromosome]["x"] = 255;
							
							$child0[$first_chromosome]["y"] += mt_rand(-RADIUS/2, RADIUS/2);
							if ($child0[$first_chromosome]["y"] < 0) $child0[$first_chromosome]["y"] = 0;
							elseif ($child0[$first_chromosome]["y"] > 255) $child0[$first_chromosome]["y"] = 255;
	
							$child1[$second_chromosome]["x"] += mt_rand(-RADIUS/2, RADIUS/2);
							if ($child1[$second_chromosome]["x"] < 0) $child1[$second_chromosome]["x"] = 0;
							elseif ($child1[$second_chromosome]["x"] > 255) $child1[$second_chromosome]["x"] = 255;
	
							$child1[$second_chromosome]["y"] += mt_rand(-RADIUS/2, RADIUS/2);											if ($child1[$second_chromosome]["y"] < 0) $child1[$second_chromosome]["y"] = 0;
							elseif ($child1[$second_chromosome]["y"] > 255) $child1[$second_chromosome]["y"] = 255;
						} // endif mutation	
						
						/*						
						echo "Generation " . $generation . " - New children for population " . $i . ": ";
						print_r($child0);
						echo " and " . ($i + 1) . ": ";
						print_r($child1);
						echo "</br>\n";
						*/
						
						/* we need to sort the points on the two childs AGAIN. Duh. And recalculate the angles.
							Duh, duh, duh */
						/*
						$child0sort = substr($child0, 1, -1);
						$child1sort = substr($child1, 1, -1);
						
						$first_individual_child0 = $child0[0];
						$first_individual_child1 = $child1[0];
						
						$last_individual_child0 = $child0[CHROMOSOMES - 1];
						$last_individual_child1 = $child1[CHROMOSOMES - 1];
						
						usort($child0sort, 'point_cmp');
						usort($child1sort, 'point_cmp');
						
						$child0 = array_merge((array)$first_individual_child0, $child0sort, 
							(array)$last_individual_child0);
						$child1 = array_merge((array)$first_individual_child1, $child1sort, 
							(array)$last_individual_child1);
						*/
						
						usort($child0, 'point_cmp');
						usort($child1, 'point_cmp');
						
						$child0[0]["angle"] = 0.0;
						$child0[1]["angle"] = 0.0;
			
						for ($j = 1; $j < CHROMOSOMES; $j++)
						{
							$child0[$j]["angle"] =
								atan2($child0[$j]["y"] - $child0[$j-1]["y"], 
									$child0[$j]["x"] - $child0[$j-1]["x"]);
							$child1[$j]["angle"] =
								atan2($child1[$j]["y"] - $child1[$j-1]["y"], 
									$child1[$j]["x"] - $child1[$j-1]["x"]);
						}
						
						// add the two children to the new population; fitness will be calculated on next iteration
						$newPopulation[$i]		= $child0;
						$newPopulation[$i+1]	= $child1;
					} // endif crossover
					else 
					{
						// no crossover, just move them directly
						$newPopulation[$i]		= $population[$i];
						$newPopulation[$i+1]	= $population[$i+1];
						// echo "No crossover for " . $i . " and " . ($i + 1) . " - moving parents to new population<br />\n"; 
					}
					// echo "<hr />\n<p>Pop " . $i . " finished</p><hr />\n";
					
				}
	/*
				echo "<hr />\n<p>Generation " . $generation . " finished</p><hr />\n";
					
				$population = $newPopulation; // prepare population
					
				$time_end = microtime(true);
				$time = $time_end - $time_start;
		
				echo "<p>CPU time used after crossover and mutation up to generation " . $generation  . ": "  . $time ." seconds</p>\n<hr />\n";
	*/
			}  // for generation
	
			echo "Final result (" . GENERATIONS ." generation(s)): <br />\n";
			showPopulation($population);
	
			// at the end, the first point (after the current position) for the last population should give us the nearest point to move to
			//  ideally, the remaining points should also have converged
			//  obviously, as the avatar moves and finds about new obstacles etc. the population will change
	
	 		
	
			// move to target; integer=1 means "walking" (never "flying")
			// 
			
			// Solution by Eduardo 20140704 — if we're close to the destination, within its radius, then we should
			//  move to the last point — which is our current destination!
			
			// Calculate where we are before we move
			$distanceToTarget = distance($curPos, $cubePosition);
			
			$target = ($distanceToTarget < RADIUS) ? CHROMOSOMES : CHROMOSOMES - 1;
			
			echo "<p class='box'>Solution: move this agent to " . print_r($population[0][1], true) . " and following " . ($target - 1) . " points. Distance is $distanceToTarget m</p>\n";
			
			for ($p = 1; $p < $target; $p++) // (skip first point — current location)
			{
				$moveResult = callURL($masterController['PermURL'], "npc=" . $agent['OwnerKey'] . "&command=osNpcMoveToTarget&vector=<" . $population[0][$p]["x"] . "," . $population[0][$p]["y"] . "," . $population[0][$p]["z"] . ">&integer=1");
				$export_rows[] = array($population[0][$p]["x"], $population[0][$p]["y"], $population[0][$p]["z"]);
				echo "<p class='box'>$p: Result from moving to (". $population[0][$p]["x"] . "," . $population[0][$p]["y"] . "," . $population[0][$p]["z"] . ") - " . $moveResult . "</p>\n";
				
				/*
				// How much should we wait? Well, we calculate the distance to the next point
				
				// ask the avatar where he is
				$curposResult = callURL($masterController['PermURL'], "npc=" . $agent['OwnerKey'] . "&command=osNpcGetPos");
				$curPos = explode(",", trim($curPos_raw, " <>()\t\n\r\0\x0B")); // sanitize
				
				
				$walkingDistance = distance(
					$curPos,
					array(
						$population[0][$p]["x"],
						$population[0][$p]["y"],
					)
				);
				$timeToTravel = ($walkingDistance / WALKING_SPEED) - 1.0; // assume the calls took 1 sec so far
				// do not wait too long, though!
				if ($timeToTravel > 2.0)
					$timeToTravel = 2.0;
				
				echo "Next point at $walkingDistance metres; waiting $timeToTravel secs for avatar to go to next point...<\br>";
				sleep($timeToTravel);*/
			}
			
	 		// Save two best solutions for next iteration; attempts to avoid to recalculate always from scratch
	 		// We do it after moving because the avatar needs a few seconds to reach destination 		
	 		
	 		// now update our database with the best paths and the target
	 		/*$SQL = "UPDATE Agents SET BestPath='" . base64_encode(serialize($population[0])) 
	 			. "', SecondBestPath='" . base64_encode(serialize($population[1]))
	 			. "', CurrentTarget='" . strtr($destCube['Position'], " ", "")
				. "' WHERE UUID='" . $agent['UUID'] . "'";
				*/
				
	//		echo "Updating database with best path, second best path, and current target for this agent...<br />";
			
			$SQL = "UPDATE Agents SET BestPath=?, SecondBestPath=?, CurrentTarget=? WHERE UUID=?";	
			try {
				$dbHandler = $db->prepare($SQL);
				
				/* echo "Preparing database SQL query: $SQL<br />\n"; */
				
				$dbHandler->execute(
					array(
						base64_encode(serialize($population[0])),
						base64_encode(serialize($population[1])),
						strtr($destCube['Position'], " ", ""),
						$agent['UUID']
					));
				/* echo "<p class='box'>Updating database with " . $SQL . " and data: BestPath= " 
						. serialize($population[0]) . "| SecondBestPath = "
						. serialize($population[1]) . "| Nearest cube = " 
						. strtr($destCube['Position'], " ", "") . "| UUID = "
						. $agent['UUID'] ."</p>\n"; */
			}
			catch(PDOException $e)
			{
				_log(__FILE__ . ":" . __LINE__ . " No rows for query $SQL");
				echo "<p class='box error'>Couldn't execute query $SQL: " . $e->getMessage() . "</p>\n";
			}	
	
	
			// See if we're close to the target; absolute precision might be impossible
			
			$curposResult = callURL($masterController['PermURL'], "npc=" . $agent['OwnerKey'] . "&command=osNpcGetPos");
			echo "<p class='box'>Grid reports that agent is at position: " . $curposResult . "</p>\n";
			
			// first, read position again, just to see what we get
	
	/*
			echo "This is how Destination Cube looks like: <br \>\n";
			var_dump($destCube);
			echo "<br />\n";
	*/		
			$currentPosition = explode(",", trim($curposResult, " ()<>"));
	
	/*
			echo "Distance comparison: Current Position:<br />\n";
			var_dump($currentPosition);
			echo "Target Cube<br />\n";
			var_dump($targetCube);
			echo "<br />\n";
	*/		
			$distance = distance($cubePosition, $currentPosition);
							
			if ($distance < 1.1) // we might never get closer than this due to rounding errors
			{
				echo "<p class='box success'>Within rounding errors of " . $destCube['Name'] . ", distance is merely $distance m; let's sit down</p>\n";
				// if we're close enough, sit on it
				$sitResult = callURL($masterController['PermURL'], "npc=" . $agent['OwnerKey'] . "&command=osNpcSit&key=" . $destCube['UUID'], "&integer=" . OS_NPC_SIT_NOW);
				echo "Result from sitting: " . $sitResult . "<br />\n";
			}
			elseif ($distance < 2.5)
			{
				echo "<p class='box warning'>Very close to " . $destCube['Name'] . ", distance is now $distance m</p>\n";	
			}
			else
			{
				echo "<p class='box warning'>Still $distance m away from " . $destCube['Name'] .	" ("
					. $cubePosition[0] . ","
					. $cubePosition[1] . ","
					. $cubePosition[2] . ")</p>\n";
			}
		
			$time_end = microtime(true);
			$time = $time_end - $time_start;
	
			echo "<p>CPU time used: $time seconds</p>\n";
			
			// Now place a button to save/export to CSV or XML
			
			
?>
	<div>
		<form name="export" action="<?php echo ROOT_URL; ?>/engine/save-engine-run.php" method="post">
	    	<input type="submit" class="ym-button ym-primary" id="submit" value="Export path to CSV">
			<input type='hidden' value='<? echo serialize($export_rows); ?>' name='export_rows'>
		</form>
	</div>
	<div>
		<a href="<?php echo ROOT_URL . '/engine/index.php?Destination=' . $_REQUEST["Destination"] . '&amp;Agent=' . $_REQUEST["Agent"]; ?>" class="ym-button ym-next">Same destination/agent</a>
	</div>
	<div>
		<a href="<?=ROOT_URL; ?>/engine/index.php" class="ym-button ym-add">Pick new destination/agent</a>
	</div>		
<?php			
		// } // foreach agent
	} // else agents
} // finish form processing
?>
<?php include ABS_PATH . "footer.php"; ?>